#include <stdio.h>
#include <stdbool.h>

#define MEM_SIZE 8096
#define BLOCK_SIZE 128

// 内存块的结构
struct Block {
    int size; // 块的大小
    bool free; // 是否空闲
    struct Block* next; // 下一个块的指针
};

// 内存池
char mem[MEM_SIZE];

// 全局链表头指针，用于跟踪内存块
struct Block* freeList = (struct Block*)mem;

// 初始化内存池
void init() {
    freeList->size = MEM_SIZE;
    freeList->free = true;
    freeList->next = NULL;
}

// 输出内存分配情况
void printMemoryStatus() {
    struct Block* curr = freeList;
    int blockNumber = 1;
    while (curr) {
        printf("Block %d - Size: %d, Free: %s\n", blockNumber, curr->size, curr->free ? "Yes" : "No");
        curr = curr->next;
        blockNumber++;
    }
}

// 分配内存函数
void* umalloc(int size) {
    struct Block* curr = freeList;
    while (curr) {
        if (curr->free && curr->size >= size) {
            if (curr->size > size + sizeof(struct Block)) {
                // 如果块的大小大于需要的大小，拆分块
                struct Block* newBlock = (struct Block*)((char*)curr + size + sizeof(struct Block));
                newBlock->size = curr->size - size - sizeof(struct Block);
                newBlock->free = true;
                newBlock->next = curr->next;
                curr->size = size;
                curr->free = false;
                curr->next = newBlock;
            } else {
                // 否则，整块分配
                curr->free = false;
            }

            printf("Allocated %d bytes in Block %d\n", size, curr->size);

            printMemoryStatus(); // 输出内存分配情况
            return (void*)(curr + 1);
        }
        curr = curr->next;
    }
    printf("Failed to allocate %d bytes. Not enough free memory.\n", size);
    return NULL; // 没有足够的可用内存
}

// 释放内存函数
void ufree(void* ptr) {
    if (ptr) {
        struct Block* curr = (struct Block*)ptr - 1;
        curr->free = true;

        printf("Freed %d bytes in Block %d\n", curr->size, curr->size);

        printMemoryStatus(); // 输出内存分配情况
    }
}

// 碎片整理函数
void umerge() {
    struct Block* curr = freeList;
    while (curr) {
        while (curr->free && curr->next && curr->next->free) {
            curr->size += curr->next->size + sizeof(struct Block);
            curr->next = curr->next->next;
        }
        curr = curr->next;
    }

    printf("Memory defragmented.\n");

    printMemoryStatus(); // 输出内存分配情况
}

int main() {
    init(); // 初始化内存池
    printf("Block own Size:%d\n",sizeof(struct Block));
    // 示例使用umalloc和ufree
    char* ptr1 = (char*)umalloc(100);
    char* ptr2 = (char*)umalloc(200);
    char* ptr3 = (char*)umalloc(300);

    ufree(ptr2); // 释放ptr2分配的内存

    umerge(); // 执行碎片整理

    return 0;
}
